/**
 * 
 */
package com.dalonedrau.graph;

import com.dalonedrau.vectors.Vector2;

/**
 * 
 * @author Donald
 *
 * @param <N>
 * @param <E>
 */
@SuppressWarnings("unchecked")
public final class SparseGraph<N extends GraphNode, E extends GraphEdge> 
implements Graph {
	/** flag indicating a node has an invalid index. */
	public static final int	INVALID_NODE_INDEX	= -1;
	/** flag indicating the graph is directed or undirected. */
	private boolean			directed;
	/**
	 * a vector of adjacency edge lists. (each node index keys into the list of
	 * edges associated with that node).
	 */
	private GraphEdge[][]		edges;
	/** the index of the next node to be added. */
	private int				nextNodeIndex;
	/** the nodes that comprise the graph. */
	private GraphNode[]		nodes;
	/** Creates a new, undirected instance of {@link SparseGraph}. */
	public SparseGraph() {
		this(false);
	}
	/**
	 * Creates a new instance of {@link SparseGraph}.
	 * @param flag flag indicating whether the graph is directed or undirected
	 */
	public SparseGraph(final boolean flag) {
		super();
		directed = flag;
		nodes = new GraphNode[0];
		edges = new GraphEdge[0][];
	}
	/**
	 * Adds an edge to the graph.
	 * @param edge the {@link GraphEdge} being added
	 * @throws Exception if the edge points to a node that was never added to
	 *         the graph
	 */
	public void addEdge(final E edge) throws Exception {
		if (edge.getFrom() >= nodes.length) {
			throw new Exception("Unable to add edge from Node "
					+ edge.getFrom()
					+ ".  That node was never added to the graph.");
		}
		if (edge.getTo() >= nodes.length) {
			throw new Exception("Unable to add edge to Node " + edge.getTo()
					+ ".  That node was never added to the graph.");
		}
		if (edges[edge.getFrom()] == null) {
			edges[edge.getFrom()] = new GraphEdge[0];
		}
		boolean canAdd = true;
		for (int i = 0; i < edges[edge.getFrom()].length; i++) {
			if (directed) {
				if (edges[edge.getFrom()][i].equalsDirected(
						edge.getFrom(), edge.getTo())) {
					canAdd = false;
					break;
				}
			} else {
				if (edges[edge.getFrom()][i].equalsUndirected(
						edge.getFrom(), edge.getTo())) {
					canAdd = false;
					break;
				}				
			}
		}
		if (canAdd) {
			// extend the length of the edges array
			GraphEdge[] src = edges[edge.getFrom()];
			GraphEdge[] dest = new GraphEdge[src.length + 1];
			System.arraycopy(src, 0, dest, 0, src.length);
			dest[src.length] = edge;
			edges[edge.getFrom()] = dest;
			dest = null;
			src = null;
		}
	}
	/**
	 * Adds a node to the graph.
	 * @param node the {@link GraphNode} to be added
	 * @throws Exception if a node has already been added with the same index.
	 */
	public void addNode(final N node) throws Exception {
		if (contains(node.getIndex())
				&& nodes[node.getIndex()].equals(node)) {
			throw new Exception("node " + node.getIndex()
					+ " already added to graph.");
		}
		if (nodes.length <= node.getIndex()) {
			// extend the length of the nodes array
			GraphNode[] dest = new GraphNode[node.getIndex() + 1];
			System.arraycopy(nodes, 0, dest, 0, nodes.length);
			nodes = dest;
			dest = null;

			// extend the length of the edges array
			GraphEdge[][] dest2 = new GraphEdge[node.getIndex() + 1][];
			System.arraycopy(edges, 0, dest2, 0, edges.length);
			edges = dest2;
			dest2 = null;
		}
		nodes[node.getIndex()] = node;
		if (node.getIndex() >= nextNodeIndex) {
			nextNodeIndex = node.getIndex() + 1;
		}
	}
	/** Clears all nodes and edges from the graph. */
	public void clear() {
		nextNodeIndex = 0;
		nodes = new GraphNode[0];
		edges = new GraphEdge[0][];
	}
	/**
	 * Determines if a node has been added to the graph at the given index.
	 * @param index the specific index
	 * @return true if the graph contains a node at the given index; false
	 *         otherwise
	 */
	public boolean contains(final int index) {
		boolean contains = false;
		if (index < nodes.length
				&& nodes[index] != null) {
			contains = true;
		}
		return contains;
	}
	/**
	 * Gets the {@link GraphEdge} defined by the provided node connection.
	 * @param from the node the edge is connecting from
	 * @param to the node the edge is connecting to
	 * @return {@link GraphEdge}
	 */
	public E getEdge(final int from, final int to) {
		E edge = null;
		// if there are edges from the node, search for a match
		if (from < edges.length
				&& edges[from] != null) {
			for (int i = 0; i < edges[from].length; i++) {
				edge = (E) edges[from][i];
				if (edge.equalsDirected(from, to)) {
					break;
				}
				edge = null;
			}
		}
		if (edge == null
				&& !directed
				&& to < edges.length
				&& edges[to] != null) {
			for (int i = 0; i < edges[to].length; i++) {
				edge = (E) edges[to][i];
				if (edge.equalsUndirected(from, to)) {
					break;
				}
				edge = null;
			}
		}
		return edge;
	}
	/**
	 * {@inheritDoc}
	 */
	public E[] getEdgesFromNode(final int index) throws Exception {
		if (index >= nodes.length) {
			throw new Exception("Node " + index
					+ " was never added to the graph.");
		}

		if (edges[index] == null) {
			edges[index] = new GraphEdge[0];
		}
		return (E[]) edges[index];
	}
	/**
	 * Gets the index of the next node to be added.
	 * @return <code>int</code>
	 */
	public int getNextFreeNodeIndex() {
		return nextNodeIndex++;
	}
	/**
	 * {@inheritDoc}
	 */
	public N getNode(final int index) {
		N node = null;
		if (index < nodes.length) {
			node = (N) nodes[index];
		}
		return node;
	}
	/**
	 * Gets the node at the given vector. If no node was added with the given 
	 * vector, <code>null</code> is returned.
	 * @param v2 the vector
	 * @return {@link GraphNode}
	 */
	public N getNode(final Vector2 v2) {
		N node = null;
		for (int i = 0; i < this.nodes.length; i++) {
			Object obj = nodes[i];
			if (obj instanceof NavGraphNode) {
				if (((NavGraphNode) obj).equals(v2)) {
					node = (N) obj;
				}
			} else {
				// this is not a navigation graph
				break;
			}
		}
		return node;
	}
	/**
	 * Gets all nodes in the graph.
	 * @return {@link GraphNode}[]
	 */
	public N[] getNodes() {
		return (N[]) nodes;
	}
	/**
	 * Returns the number of active nodes present in the graph.
	 * @return <code>int</code>
	 */
	public int getNumberOfActiveNodes() {
		int count = 0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null
					&& ((N) nodes[i]).getIndex()
					!= SparseGraph.INVALID_NODE_INDEX) {
				count++;
			}
		}
		return count;
	}
	/**
	 * Gets the number of edges in the graph.
	 * @return <code>int</code>
	 */
	public int getNumberOfEdges() {
		int count = 0;
		for (int outer = 0; outer < edges.length; outer++) {
			E[] list = (E[]) edges[outer];
			for (int inner = 0; inner < list.length; inner++) {
				if (list[inner] != null
						&& list[inner].getTo()
						!= SparseGraph.INVALID_NODE_INDEX) {
					count++;
				}
			}
		}
		return count;
	}
	/**
	 * {@inheritDoc}
	 */
	public int getNumberOfNodes() {
		int count = 0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i] != null) {
				count++;
			}
		}
		return count;
	}
	/**
	 * Determines if the graph is directed or undirected.
	 * @return true of the graph is directed; false otherwise
	 */
	public boolean isDirected() {
		return directed;
	}
	/**
	 * Determines if this graph contains no nodes.
	 * @return true if the graph has no nodes, active or inactive; false
	 *         otherwise
	 */
	public boolean isEmpty() {
		boolean isEmpty = false;
		if (getNumberOfNodes() == 0) {
			isEmpty = true;
		}
		return isEmpty;
	}
	/**
	 * Removes an edge from the list of edges.
	 * @param from the node the edge is connecting from
	 * @param to the node the edge is connecting to
	 */
	public void removeEdge(final int from, final int to) {
		if (getEdge(from, to) != null) {
			for (int i = 0; i < edges[from].length; i++) {
				E edge = (E) edges[from][i];
				if (edge.getTo() == to) {
					edge.setTo(SparseGraph.INVALID_NODE_INDEX);
					break;
				}
			}
		}
		if (!directed) {
			if (getEdge(to, from) != null) {
				for (int i = 0; i < edges[to].length; i++) {
					E edge = (E) edges[to][i];
					if (edge.getTo() == from) {
						edge.setTo(SparseGraph.INVALID_NODE_INDEX);
						break;
					}
				}
			}
		}
	}
	/**
	 * Removes a {@link GraphNode} from the graph.
	 * @param index the node index
	 * @throws Exception if the node being removed was never added to the graph
	 */
	public void removeNode(final int index) throws Exception {
		if (index >= nodes.length) {
			throw new Exception("Node " + index
					+ " was never added to the graph.");
		}
		if (nodes[index] == null) {
			throw new Exception("Node " + index
					+ " was never added to the graph.");
		}
		((N) nodes[index]).setIndex(SparseGraph.INVALID_NODE_INDEX);
	}
	/**
	 * Replaces a node within the graph.
	 * @param node the {@link GraphNode} to be added
	 * @throws Exception if no node with the given node was previously added to
	 *         the graph
	 */
	public void replaceNode(final GraphNode node) throws Exception {
		if (contains(node.getIndex())
				&& nodes[node.getIndex()].equals(node)) {
			nodes[node.getIndex()] = node;
		} else {
			throw new Exception("Node " + node.getIndex()
					+ " was never added to the graph.");
		}
	}
}
